﻿/*******************************************************************
 *     JameE
 *******************************************************************
  Copyright 2010 Clifford Champion and JameE contributors.
  
  This file is part of JameE.
  
  JameE is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
  
  JameE is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with JameE.  If not, see <http://www.gnu.org/licenses/>.
 ******************************************************************/

/// <reference path="../Base/Classer.js" />
/// <reference path="../Base/IncludeLoader.js" />

$class(
"JameE.Math.Graph$Vertex",
{
	oPosition: null,
	arr_iEdgeIds: null,
	_ctor: function () {
		this.oPosition = $argument("position", "Math.Vector3");
		this.arr_iEdgeIds = [];
	}
});

$class(
"JameE.Math.Graph",
{
	/////////////////////
	// CONSTANTS
	/////////////
	ID_MAX_VALUE: 0x0000FFFF,


	/////////////////////
	// FIELDS
	/////////////
	_iVertexIdCounter: 0,

	_hash_oVertices: null, // [JameE.Math.Graph$Vertex, ...]
	_hash_oEdges: null, // [ {fromId << 16 | toId}, ...]

	_hash_oVertexUserData: null,
	_hash_oEdgeUserData: null,


	/////////////////////
	// CONSTRUCTORS
	/////////////
	_ctor: function () {
		this.clear();
	},


	/////////////////////
	// METHODS
	/////////////
	clear: function () {
		this._iVertexIdCounter = 0;
		this._hash_oVertices = {};
		this._hash_oEdges = {};
		this._hash_oVertexUserData = {};
		this._hash_oEdgeUserData = {};
	},

	addVertex: function (oVertexA) {
		/// <summary>Adds a new vertex.</summary>
		$require_type(oVertexA, "Vector3");

		// add vertex
		iVertexId = ++this._iVertexIdCounter;
		if (iVertexId > this.ID_MAX_VALUE) {
			throw new Error("ID_MAX_VALUE reached.");
		}
		this._hash_oVertices[iVertexId]
			= new JameE.Math.Graph$Vertex(
				{
					position: oVertexA
				}
			)
		;

		// done. return vertex id.
		return iVertexId;
	},

	addVertexBatch: function (arr_oPositions) {
		$require_type(arr_oPositions, "array");

		var iLength = arr_oPositions.length;
		for (var i = 0; i < iLength; ++i) {
			this.addVertex(arr_oPositions[i]);
		}
	},

	addVerticesAndEdge: function (oVertexA, oVertexB) {
		/// <summary>Adds two vertices and an edge connecting them.</summary>

		var iVertexA = this.addVertex(oVertexA);
		var iVertexB = this.addVertex(oVertexB);

		this.addEdge(iVertexA, iVertexB);
	},

	addEdge: function (iVertexIdA, iVertexIdB) {
		/// <summary>Adds an edge between the given vertices (by id).</summary>

		// form edge key
		var iEdgeKey = (iVertexIdA << 16) | iVertexIdB;

		// add edge
		if (!this._hash_oEdges.hasOwnProperty(iEdgeKey)) {
			this._hash_oEdges[iEdgeKey] = true;

			// add edge to the vertex entries
			this._hash_oVertices[iVertexIdA].arr_iEdgeIds.push(iEdgeKey);
			this._hash_oVertices[iVertexIdB].arr_iEdgeIds.push(iEdgeKey);
		}
		return iEdgeKey;
	},

	updateVertex: function (iVertexId, oPosition) {
		/// <summary>Updates an existing vertex's position.</summary>
		$require_type(iVertexId, "number");
		$require_type(oPosition, "Math.Vector3");

		var oVertex = this._hash_oVertices[iVertexId] || null;
		if (oVertex === null) {
			throw new Error("Vertex not found.");
		}
		oVertex.oPosition = oPosition;
	},

	findVertexId: function (oVector3) {
		/// <summary>Locates the id of the given vertex coordinates, or -1 if not found.</summary>

		for (var id in this._hash_oVertices) {
			var oCurrentVector = this._hash_oVertices[id].oPosition;
			if (oCurrentVector.equals(oVector3)) {
				return id;
			}
		}
		return -1;
	},

	getVertex: function (iVertexId) {
		/// <summary>Returns the vertex Vector3 of the corresponding given Id.</summary>

		var oVertexEntry = this._hash_oVertices[iVertexId] || null;
		if (oVertexEntry) {
			return oVertexEntry.oPosition;
		}
		else {
			return null;
		}
	},

	removeVertex: function (oVertex) {
		/// <summary>Removes the given vertex (by Id or position).</summary>

		var iVertexId;
		if (typeof (oVertex) === "number") {
			iVertexId = oVertex;
		}
		else {
			iVertexId = this.findVertexId(oVertex);
			if (iVertexId === -1) {
				return;
			}
		}

		// remove edges that use this vertex
		for (var iEdgeId in this._hash_oEdges) {
			if (((iEdgeId >> 16) === iVertexId)
			|| (iEdge & 0x0000FFFF == iVertexId)) {
				delete this._hash_oEdges[iEdgeId];
				delete this._hash_oEdgeUserData[iEdgeId];
			}
		}

		// remove vertex
		delete this._hash_oVertices[iVertexId];
		delete this._hash_oVertexUserData[iVertexId];
	},

	removeEdge: function (iEdgeId) {
		/// <summary>Removes the given edge (by id).</summary>

		// lookup the vertices involved and remove the edge
		var oVertexA = this._hash_oVertices[(iEdgeId << 16)];
		var oVertexB = this._hash_oVertices[(iEdgeId & 0x0000FFFF)];

		JameE.Utils.Array.removeElement(oVertexA.arr_iEdgeIds, iEdgeId);
		JameE.Utils.Array.removeElement(oVertexB.arr_iEdgeIds, iEdgeId);

		delete this._hash_oEdges[iEdgeId];
		delete this._hash_oEdgeUserData[iEdgeId];
	},

	forEachVertex: function (fnCallback) {
		/// <summary>Executes the callback method for each vertex, passing 
		/// to it the vertex Vector3.
		/// fnCallback(iId, oPosition)
		/// </summary>

		$require_type(fnCallback, "function");
		for (var iKey in this._hash_oVertices) {
			var bContinue = fnCallback(parseInt(iKey), this._hash_oVertices[iKey].oPosition) || true;
			if (!bContinue) { break; }
		}
	},

	forEachEdge: function (fnCallback) {
		/// <summary>Executes the callback method for each edge, passing
		/// to it an id for each edge, and the two vertices as Vector3's.</summary>
		$require_type(fnCallback, "function");
		for (var iKey in this._hash_oEdges) {
			if (!this._hash_oEdges.hasOwnProperty(iKey)) {
				continue;
			}
			iKey = parseInt(iKey);
			var iVertexIdA = iKey >> 16;
			var iVertexIdB = 0x0000FFFF & iKey;

			var oVertexA = this.getVertex(iVertexIdA);
			var oVertexB = this.getVertex(iVertexIdB);

			var bContinue = fnCallback(iKey, oVertexA, oVertexB) || true;
			if (!bContinue) { break; }
		}
	},

	forEachEdgeOfVertex: function (iVertexId, fnCallback) {
		$require_type(iVertexId, "number");
		$require_type(fnCallback, "function");

		var oVertex = this._hash_oVertices[iVertexId];
		var iNumEdges = oVertex.arr_iEdgeIds.length;
		for (var i = 0; i < iNumEdges; ++i) {
			var iEdgeId = oVertex.arr_iEdgeIds[i];
			var iVertexIdA = iEdgeId >> 16;
			var iVertexIdB = 0x0000FFFF & iEdgeId;

			var oVertexA = this.getVertex(iVertexIdA);
			var oVertexB = this.getVertex(iVertexIdB);

			var bContinue = fnCallback(iEdgeId, iVertexIdA, oVertexA, iVertexIdB, oVertexB) || true;
			if (!bContinue) { break; }

		}
	},

	findNearestVertex: function (oPoint) {
		/// <summary>Returns the vertex id of the vertex nearest the given point.</summary>

		// todo: optimize this garbage!

		var fBestDistanceSquared = Number.MAX_VALUE;
		var iBestVertexId = this.ID_MAX_VALUE;

		this.forEachVertex(
			function (iId, oPosition) {
				var fDistanceSquared = oPosition.subtract(oPoint).magnitudeSquared();
				if (fDistanceSquared < fBestDistanceSquared) {
					fBestDistanceSquared = fDistanceSquared;
					iBestVertexId = iId;
				}
			}
		);

		if (iBestVertexId === this.ID_MAX_VALUE) {
			return null;
		}
		else {
			return iBestVertexId;
		}
	},

	getVertexData: function (iVertexId) {
		/// <summary>Returns the user data associated with this vertex.</summary>
		$require_type(iVertexId, "number");
		return this._hash_oVertexUserData[iVertexId];
	},

	setVertexData: function (iVertexId, oData) {
		/// <summary>Sets the user data for this vertex.</summary>
		$require_type(iVertexId, "number");
		this._hash_oVertexUserData[iVertexId] = oData;
	},

	getEdgeData: function (iEdgeId) {
		/// <summary>Returns the user data associated with this edge.</summary>
		$require_type(iEdgeId, "number");
		return this._hash_oEdgeUserData[iEdgeId];
	},

	setEdgeData: function (iEdgeId, oData) {
		/// <summary>Sets the user data associated for this edge.</summary>
		$require_type(iEdgeId, "number");
		this._hash_oEdgeUserData[iEdgeId] = oData;
	}
});

$include_notify("Math/Graph.js");

